class Solution
{
public:
    bool validateStackSequences(vector<int> &pushed, vector<int> &popped)
    {
        vector<int> stack;
        stack.reserve(pushed.size());
        auto pushIn = pushed.begin();
        for (int num : popped)
        {
            while (true)
            {
                if (!stack.empty())
                {
                    if (num == stack.back())
                    {
                        stack.pop_back();
                        break;
                    }
                    else if (pushIn == pushed.end())
                    {
                        return false;
                    }
                    else
                    {
                        stack.push_back(*pushIn);
                        ++pushIn;
                    }
                }
                else if (pushIn == pushed.end()) // 理论上不会出现
                {
                    return false;
                }
                else
                {
                    stack.push_back(*pushIn);
                    ++pushIn;
                }
            }
        }
        return true;
    }
};